class UnionFind {
    constructor(n){
        this.father = new Array(n)
        this.rank = new Array(n)
        for(let i=0; i<n; i++){
            this.father[i] = i
            this.rank[i] = i
        }
    }

    find(x){
        if(x<0 || x>=this.father.length){
            throw new TypeError("查询越界了")
        }
        while(x != this.father[x]){
            this.father[x] = this.father[this.father[x]]
            x = this.father[x]
        }
        return x
    }

    union(x, y){
        let fx = this.find(x)
        let fy = this.find(y)
        if(fx == fy) return
        if(fx == undefined || fy == undefined) return
        if(this.rank[fx] < this.rank[fy]){
            this.father[fx] = fy
        }else if(this.rank[fx] > this.rank[fy] ){
            this.father[fy] = fx
        }else{
            this.father[fy] = fx
            this.rank[fx] += 1
        }
    }
}

function trulyMostPopular(names, synonyms) {
    let namesLen = names.length
    const nameToIndex = new Map()
    const nameToNum = new Map()
    let count = 0
    
    for(let i=0; i<namesLen; i++){
        let name_num = names[i].split('(')
        let name = name_num[0]
        let num = name_num[1].split(')')[0]
        nameToIndex.set(name, count++)
        nameToNum.set(name, num)
    }

    for(let i=0; i<synonyms.length; i++){
        let synonym = synonyms[i].split(',')
        let nameX = synonym[0].split('(')[1]
        let nameY = synonym[1].split(')')[0]
        if(!nameToIndex.has(nameX)){
            nameToIndex.set(nameX, count++)
            nameToNum.set(nameX, 0)
        }
        if(!nameToIndex.has(nameY)){
            nameToIndex.set(nameY, count++)
            nameToNum.set(nameY, 0)
        }
    }

    const uf = new UnionFind(count)
    console.log(uf.father)
    // 合并
    for(let i=0; i<synonyms.length; i++){
        let synonym = synonyms[i].split(',')
        let nameX = synonym[0].split('(')[1]
        let nameY = synonym[1].split(')')[0]
        let indexX = nameToIndex.get(nameX)
        let indexY = nameToIndex.get(nameY)
        uf.union(indexX, indexY)
    }
    const indexToNames = new Map()
    for (const [name, index] of nameToIndex) {
        let indexRoot = uf.find(index)
        const names = [name]
        if(indexToNames.has(indexRoot)){
            indexToNames.get(indexRoot).forEach(existName => {
                names.push(existName)
            });
        }
        indexToNames.set(indexRoot, names.sort())
    }
    console.log(uf.father)
    console.log(indexToNames)
    const returnArr = []
    for (const [index, names] of indexToNames) {
        let num = 0
        names.forEach(name => {
            num += parseInt(nameToNum.get(name))
        });
        returnArr.push(names[0] + '(' + num.toString() + ')')
    }
    console.log(returnArr)
};



const names = ["a(10)","c(13)"]

const synonyms = ["(a,b)","(c,d)","(b,c)"]
trulyMostPopular(names, synonyms)
